package pers.qianyu.month_202011.date_20201118;

import java.util.*;

/**
 * 56. 合并区间
 * https://leetcode-cn.com/problems/merge-intervals/
 *
 * @author mizzle rain
 * @date 2020-11-18 13:28
 */
public class Merge {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, (item1, item2) -> {
            int a = item1[0] - item2[0];
            return a == 0 ? item2[1] - item1[1] : a;
        });
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            int[] pre = res.get(res.size() - 1);
            if (cur[0] > pre[1]) {
                res.add(cur);
            } else {
                // 合并
                res.remove(pre);
                res.add(new int[]{pre[0], Math.max(cur[1], pre[1])});
            }
        }
        return res.toArray(new int[0][0]);
    }

    /**
     * 细节优化
     */
    public int[][] merge2(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, Comparator.comparingInt(item -> item[0]));
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            int[] pre = res.get(res.size() - 1);
            if (cur[0] > pre[1]) {
                res.add(cur);
            } else {
                // 合并
                pre[1] = Math.max(cur[1], pre[1]);
            }
        }
        return res.toArray(new int[0][0]);
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 4}, {0, 2}, {3, 5}};
        int[][] result = new Merge().merge(arr);
        System.out.println("result = " + Arrays.deepToString(result));
    }
}
